package leetcode.other.p49;

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 遍历strs数组，每个str都还原成字典序，相同字典序的str归到一起
        // 用map记录
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String dictOrderStr = getDictOrderStr(str);
            List<String> list = map.computeIfAbsent(dictOrderStr, p -> new ArrayList<>());
            list.add(str);
        }

        return new ArrayList<>(map.values());
    }

    private String getDictOrderStr(String str) {
        char[] sortedChars = str.toCharArray();
        Arrays.sort(sortedChars);
        return new String(sortedChars);
    }

    public static void main(String[] args) {
        // 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
        // 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
        System.out.println(new Solution().groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
    }
}